/*
https://leetcode-cn.com/problems/divide-two-integers/solution/liang-shu-xiang-chu-by-leetcode-solution-5hic/
 */
public class Solution29 {
    public int divide(int dividend, int divisor) {
        if (dividend==Integer.MIN_VALUE){
            if (divisor==1){
                return Integer.MIN_VALUE;
            }
            if (divisor==-1){
                return Integer.MAX_VALUE;
            }
        }
        if (divisor==Integer.MIN_VALUE){
            return dividend==Integer.MIN_VALUE?1:0;
        }
        if (dividend==0){
            return 0;
        }
        boolean rev=false;
        if (dividend>0){
            rev=!rev;
            dividend=-dividend;
        }
        if (divisor>0){
            rev=!rev;
            divisor=-divisor;
        }

        int l=1,r=Integer.MAX_VALUE,ans=0;
        while (l<=r){
            int mid=l+((r-l)>>1);
            if (check(divisor,mid,dividend)){
                ans=mid;
                if (mid==Integer.MAX_VALUE){
                    break;
                }
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return rev? -ans:ans;
    }

    boolean check(int a,int b,int c){
        int result=0,add=a;
        while(b!=0){
            if ((b&1)!=0){
                if (result<c-add){
                    return false;
                }
                result+=add;
            }
            if (b!=1){
                if (add<c-add){
                    return false;
                }
                add+=add;
            }
            b>>=1;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution29().divide(7,-3));
    }
}
